package com.zs.letcode.top_interview_questions;

import java.util.*;
import java.util.concurrent.PriorityBlockingQueue;

/**
 * 数据流的中位数
 * 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
 * <p>
 * 例如，
 * <p>
 * [2,3,4]的中位数是 3
 * <p>
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 * <p>
 * 设计一个支持以下两种操作的数据结构：
 * <p>
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 示例：
 * <p>
 * addNum(1)
 * addNum(2)
 * findMedian() -> 1.5
 * addNum(3)
 * findMedian() -> 2
 * 进阶:
 * <p>
 * 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
 * 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
 * 相关标签
 * 堆
 * 设计
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xalff2/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/1 09:57
 */
public class Chapter27 {
    public static void main(String[] args) {
        MedianFinder obj = new MedianFinder();
        obj.addNum(2);
        obj.addNum(1);
        obj.addNum(3);
        obj.addNum(8);
        obj.addNum(9);
        double param_2 = obj.findMedian();
        System.out.println(param_2);

        Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        queue.add(2);
        queue.add(23);
        queue.add(4);
        queue.add(6);
        queue.add(7);
        queue.add(5);
        System.out.println(queue);
        System.out.println(queue.peek());

        Queue<Integer> queue1 = new PriorityQueue<>();
//        queue1.add(null);
        Deque<Integer> deque0 = new ArrayDeque<>();
//        deque0.add(null);
        Deque<Integer> deque1 = new LinkedList<>();
        deque1.add(null);
        System.out.println(deque1);

        Set<Integer> set0 = new LinkedHashSet<>();
        Set<Integer> set1 = new TreeSet<>();
    }

    private static class MedianFinder {
        // 方法一：简单排序
        private List<Integer> nums;
        // 方法三：两个堆
        Queue<Integer> lo;
        Queue<Integer> hi;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
//            nums = new ArrayList<>();
            lo = new PriorityQueue<>();
            hi = new PriorityQueue<>((a, b) -> b - a);
        }

        public void addNum(int num) {
//            nums.add(num);
            if (hi.isEmpty()) {
                hi.add(num);
                return;
            }
            if (num <= hi.peek()) {
                // 到这里，说明 num 属于较小的元素，所以存储在大顶堆
                hi.add(num);
            } else {
                // 到这里，num 属于较大的元素
                lo.add(num);
            }

            // 维护好两个堆中的元素个数，原则：
            // 1. 如果是有偶数个元素的话，那么大顶堆和小顶堆是相同的
            // 2. 如果是有奇数个元素的话，那么大顶堆元素的个数比小顶堆多 1 个
            if (hi.size() > lo.size() + 1) {
                lo.add(hi.remove());
            }
            if (hi.size() < lo.size()) {
                hi.add(lo.remove());
            }
        }

        public double findMedian() {
//            Collections.sort(nums);
//            int n = nums.size();
//            return (n % 2 == 1 ? nums.get(n / 2) : (nums.get(n / 2 - 1) + nums.get(n / 2)) * 0.5);

            return hi.size() > lo.size() ? hi.peek().doubleValue() : (hi.peek() + lo.peek() * 0.5);
        }
    }

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
}
